#include <stdio.h>
#include <iostream.h>
#include <string.h>
#include <conio.h>
#include <stdlib.h>
#define so_canh_toida 100
typedef struct {
	int dau;
	int cuoi;
	int trongso;
} canh;
typedef struct {
	int sodinh;
	int tdinh[100];
	int socanh;
	canh dscanh[so_canh_toida];
} dothi;
void nhap_do_thi(dothi &dt)
//doc noi dung file va dua vao do thi

{
	char str1[255];
	FILE *fb = fopen("graph.txt","rt");
	if (fb == NULL) {
		printf("Mo file ko thanh cong");
		return;
	}
	fscanf(fb,"%d%d", &dt.sodinh,&dt.socanh);

	//tao ten cua cac dinh trong do thi
	for(int j=0;j<dt.sodinh;j++)
	{
		dt.tdinh[j] = j+1;
	}

	for (int i=0;i<dt.socanh;i++)
	{
		fscanf(fb,"%d%d%d",&dt.dscanh[i].dau,&dt.dscanh[i].cuoi,&dt.dscanh[i].trongso);
	}
	
}
void in_do_thi(dothi dt)
{
	cout<<"so dinh cua do thi: "<<dt.sodinh<<endl;
	cout<<"so canh cua do thi: "<<dt.socanh<<endl;
	cout<<"Tap cac dinh cua do thi: { ";
	for(int i=0;i<dt.sodinh;i++) cout<<dt.tdinh[i]<<" ";
	cout<<"}"<<endl;
	cout<<"Tap cac canh cua do thi: "<<endl;
	for(int i=0;i<dt.socanh;i++)
	{
		cout<<"canh "<<i+1<<": "<<dt.dscanh[i].dau<<"  "<<dt.dscanh[i].cuoi<<"  ";
		cout<<dt.dscanh[i].trongso<<endl;
	}
}
void sap_xep_canh_dothi(dothi &G)
{
	canh tam;
	for (int i=0;i<G.socanh-1;i++)
		for(int j=i+1;j<G.socanh;j++)
		{
			if(G.dscanh[i].trongso > G.dscanh[j].trongso)
			{
				tam =G.dscanh[i];
				G.dscanh[i]= G.dscanh[j];
				G.dscanh[j]=tam;
			}
		}
}
int tong_tso(dothi G)
{
	int tam = 0;
	for(int i=0;i<G.socanh;i++) tam += G.dscanh[i].trongso;
	return tam;
}
int getroot(int dinh_a, int lab[]) //tra ve goc cua cay T co chua dinh_a
{
	while(lab[dinh_a] > 0) dinh_a = lab[dinh_a];
	return dinh_a;		
}
void hop_2cay(int r1, int r2, int lab[]) //hop 2 cay co goc r1 va r2
{
	int x = lab[r1] + lab[r2];
	if (lab[r1] > lab[r2])//cay r1 co so nut it hon cay r2
	{
		lab[r1] = r2; //cha cua r1 la r2
		lab[r2] = x; //r2 la cay moi va -lab[r2] la tong so nut cua cay moi
	}
	else
	{
		lab[r2] = r1; //cha cua r2 la r1
		lab[r1] = x; //r1 la cay moi va -lab[r1] la tong so nut cua cay moi		
	}
}
int tt_kruskal(dothi &G, dothi &T) // ham tra ve 0 neu do thi ko lien thong
{
	canh tam;
	//khoi tao cay khung T ban dau
	T.sodinh = G.sodinh;//so dinh cua T ban dau la so dinh cua G
	for(int i=0;i<G.sodinh;i++) T.tdinh[i]=G.tdinh[i]; //tap dinh T = tap dinh G
	T.socanh = 0;//so canh trong T ban dau = rong
	int lab[100];
	for(int i=0;i<T.sodinh;i++) lab[i+1] = -1;//cac dinh trong T coi nhu la cac cay doc lap co 1 goc
	
	//giai thuat KRUSKAL ////
	sap_xep_canh_dothi(G);//sap xep tang cac canh do thi G theo trong so
	
	int i=0;
	do {
		tam = G.dscanh[i];
		int r1 = getroot(tam.dau,lab);
		int r2 = getroot(tam.cuoi,lab);
		if (r1 != r2 )//2 dinh cua canh moi co 2 goc khac nhau => k tao chu trinh
		{
			//them canh tam vao T
			T.dscanh[T.socanh++] = tam;
			//hop nhat 2 cay goc r1 va r2 thanh 1 cay	
			hop_2cay(r1,r2,lab);
		}
		i++;
	} while ((T.socanh < G.sodinh-1) && (i<G.socanh));
	return (T.socanh == G.sodinh-1);
}
int main()
{
    
    dothi G,T;
    nhap_do_thi(G);
 	cout<<"DO THI G BAN DAU:"<<endl;
	in_do_thi(G);
	
    //sap_xep_canh_dothi(G);
	cout<<"CAY KHUNG T BANG THUAT TOAN kruskal:"<<endl;
	if (tt_kruskal(G,T)==0) cout<<"Do thi ko lien thong"<<endl;
	else
	{
		in_do_thi(T);	
		cout<<"Trong so cua T la: "<<tong_tso(T)<<endl;
	}
    return 1;
}